package leetcode.offer_two_special.dp;

import java.util.Arrays;

/**
 * @author mazouri
 * @create 2021-09-20 19:08
 */
public class _102_findTargetSumWays {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

        if (Math.abs(target) > sum) return 0;

        int row = nums.length;
        int col = sum * 2 + 1;

        int[][] dp = new int[row][col];
        dp[0][sum + nums[0]]++;
        dp[0][sum - nums[0]]++;

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //防止角标越界
                int l = (j - nums[i]) < 0 ? 0 : j - nums[i];
                int r = (j + nums[i]) >= col ? 0 : j + nums[i];
                dp[i][j] = dp[i - 1][l]+dp[i - 1][r];
            }
        }

        return dp[nums.length-1][sum+target];
    }
}
